package AlgorithmCenter;

public class Algorithm20200916 {

    /*
       n的m划分问题（n个同样的苹果放入m个同样的盘子中问题）
       状态转移方程：
       设dp[n][m]表示将n个苹果放入m个盘子的放法数
       dp[n][m]=dp[n][n] (m>n)
       dp[n][m]=dp[n-m][m]+dp[n][m-1] (m<=n)
     */
    public int NumberOfDivisionsQues(int n,int m)
    {
        int[][] dp=new int[n+1][m+1];
        dp[0][0]=1;
        for (int i = 0; i <=n ; i++) {
            for (int j = 1; j <=m ; j++) {
                if(i==1||i==0)
                {
                    //只有一个苹果的话那么只存在一种分配方法
                    dp[i][j]=1;
                }
                else
                {
                    if(j>i)
                    {
                        dp[i][j]=dp[i][i];
                    }
                    else
                    {
                        dp[i][j]=dp[i-j][j]+dp[i][j-1];
                    }

                }

            }
        }
        return dp[n][m];
    }

}
